import java.util.Random;
import java.text.DecimalFormat;


public class MaxSubSum {

    static private int seqStart = 0;
    static private int seqEnd = -1;

    /**
     * Cubic maximum contiguous subsequence sum algorithm.
     * seqStart and seqEnd represent the actual best sequence.
     */
    public static int maxSubSum3( int [ ] a )
    {
        int maxSum = 0;

        for( int i = 0; i < a.length; i++ )
            for( int j = i; j < a.length; j++ )
            {
                int thisSum = 0;

                for( int k = i; k <= j; k++ )
                    thisSum += a[ k ];

                if( thisSum > maxSum )
                {
                    maxSum   = thisSum;
                    seqStart = i;
                    seqEnd   = j;
                }
            }

        return maxSum;
    }


    /**
     * Quadratic maximum contiguous subsequence sum algorithm.
     * seqStart and seqEnd represent the actual best sequence.
     */
    public static int maxSubSum2( int [ ] a )
    {
        int maxSum = 0;

        for( int i = 0; i < a.length; i++ )
        {
            int thisSum = 0;
            for( int j = i; j < a.length; j++ )
            {
                thisSum += a[ j ];

                if( thisSum > maxSum )
                {
                    maxSum = thisSum;
                    seqStart = i;
                    seqEnd   = j;
                }
            }
        }

        return maxSum;
    }

    /**
     * Linear-time maximum contiguous subsequence sum algorithm.
     * seqStart and seqEnd represent the actual best sequence.
     */
    public static int maxSubSum1( int [ ] a )
    {
        int maxSum = 0;
        int thisSum = 0;

        for( int i = 0, j = 0; j < a.length; j++ )
        {
            thisSum += a[ j ];

            if( thisSum > maxSum )
            {
                maxSum = thisSum;
                seqStart = i;
                seqEnd   = j;
            }
            else if( thisSum < 0 )
            {
                i = j + 1;
                thisSum = 0;
            }
        }

        return maxSum;
    }

    public static void main(String[] args) {
		int[] sizes = {100, 1000, 5000, 10000, 20000, 30000, 40000, 50000};
		DecimalFormat formatter = new DecimalFormat("0.00000000");
		
		for (int i=0; i < sizes.length; ++i) {
			int N = sizes[i];
			
	        int[] a = new int[N];
    	    Random rand = new Random();

        	for (int j=0; j < a.length; ++j) {
            	a[j] = rand.nextInt() % 10;
        	}

			long start = System.currentTimeMillis();
			int maxSum = maxSubSum2(a);
			long T = System.currentTimeMillis() - start;

			double TdivN = ((double)T)/((double)N);
			double TdivN2 = ((double)T)/((double)N*(double)N);
			double TdivN3 = ((double)T)/((double)N*(double)N*(double)N);

			System.out.println("T/N = " + formatter.format(TdivN) +
							   "\tT/N2 = " + formatter.format(TdivN2) +
							   "\tT/N3 = " + formatter.format(TdivN3));
		}
    }
}